package graphic;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 你被给定一个 m × n 的二维网格，网格中有以下三种可能的初始化值：
 *
 * -1 表示墙或是障碍物
 * 0 表示一扇门
 * INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。
 * 你要给每个空房间位上填上该房间到 最近 门的距离，如果无法到达门，则填 INF 即可。
 *
 * 示例：
 *
 * 给定二维网格：
 *
 * INF  -1  0  INF
 * INF INF INF  -1
 * INF  -1 INF  -1
 *   0  -1 INF INF
 * 运行完你的函数后，该网格应该变成：
 *
 *   3  -1   0   1
 *   2   2   1  -1
 *   1  -1   2  -1
 *   0  -1   3   4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/walls-and-gates
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class WallsAndGates {

    int[][] dir = new int[][]{{-1,0}, {1,0}, {0, -1}, {0, 1}};
    public void wallsAndGates(int[][] rooms) {

        if(rooms == null || rooms.length == 0 || rooms[0].length == 0){
            return;
        }

        Queue<int[]> queue = new ArrayDeque<>();
        for(int i = 0; i < rooms.length; i ++){
            for(int j = 0; j < rooms[0].length; j++){
                if(rooms[i][j] == 0){
                    queue.add(new int[]{i, j});
                }
            }
        }
        while(!queue.isEmpty()){
            int[] point = queue.poll();

            for(int i = 0; i < 4; i ++){
                int row = point[0] + dir[i][0];
                int col = point[1] + dir[i][1];
                if(row < 0 || col < 0 || row > rooms.length - 1 || col > rooms[0].length - 1 || rooms[row][col] != Integer.MAX_VALUE){
                    continue;
                }
                rooms[row][col] = rooms[point[0]][point[1]] + 1;
                queue.add(new int[]{row, col});
            }
        }
    }

    public static void main(String[] args){
        int[][] rooms = new int[][]{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1},{2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}};
        (new WallsAndGates()).wallsAndGates(rooms);
    }
}
